# 07. 买卖股票的最佳时机
# 这题的最优解是逆向思维，颇有动态规划的思维。
# 进行一次遍历，假设每次遍历到的是要卖出的哪一天，那么最优的买入的日期就是从第一天到这天中价格最低的哪一天。
# 并且这个最低的一天可以在每次遍历的时候依次对比！
from typing import List
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        current_min_price = prices[0]
        ans = 0
        length = len(prices)
        for i in range(len(prices)):
            ans = max(ans, prices[i] - current_min_price)
            current_min_price = min(current_min_price, prices[i])
        return ans